# https://leetcode.cn/problems/jump-game-ii/
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        if len(nums) <= 1:
            return 0

        min_jumps = [0] * len(nums)
        for idx in range(0, len(nums)):
            num = nums[idx]

            for step in range(1, num + 1):
                step_idx = min(idx + step, len(nums) - 1)
                if min_jumps[step_idx] == 0:
                    min_jumps[step_idx] = min_jumps[idx] + 1
                else:
                    min_jumps[step_idx] = min(min_jumps[idx] + 1, min_jumps[step_idx])
        return min_jumps[-1]
